﻿using System;
using System.Collections.Generic;
using GeneticAlgorithms.Genomes;
using GeneticAlgorithms.Populations;
using GeneticAlgorithms.Tools;

namespace GeneticAlgorithms.Operators.Selection
{
    /// <summary>
    /// Implements roulette selection.
    /// </summary>
    /// <typeparam name="TGenome">The type of the genome.</typeparam>
    /// <typeparam name="TGene">The type of the gene.</typeparam>
    public class RouletteSelector<TGenome, TGene> : IGeneticSelector<TGenome, TGene> where TGenome : IGenome<TGene>
    {
        #region IGeneticSelector<TGene> Members

        /// <summary>
        /// Selects the genomes.
        /// </summary>
        /// <param name="population">The population from which
        /// the selected genomes will be picked.</param>
        /// <param name="selectCount">The count of genomes to select.</param>
        /// <returns>A genome of selected genomes.</returns>
        public IEnumerable<TGenome> SelectGenomes(
            IPopulation<TGenome, TGene> population,
            int selectCount)
        {
            double[] accumulatedFitness = new double[population.Count];
            List<TGenome> result = new List<TGenome>(population.Count);

            double acc = 0;

            int i;

            for (i = 0; i < population.Count; ++i)
            {
                acc += population[i].Fitness.Value;
                accumulatedFitness[i] = acc;
            }

            // selecting the genomes
            for (i = 0; i < selectCount; ++i)
            {
                double val = GeneticRandomGenerator.Default.NextDouble() * acc;
                int pos = Array.BinarySearch<double>(accumulatedFitness, 0, population.Count, val);
                if (pos < 0)
                {
                    pos = ~pos;
                }

                result.Add(population[pos]);
            }

            return result;
        }

        #endregion
    }
}
